package cn.com.mdx.sort.practice.nutsbolts;

import edu.princeton.cs.algs4.StdRandom;

import java.util.ArrayList;
import java.util.List;

/**
 * <p> 木匠
 *
 * @author ：huangy
 * @date ：Created in 2020/9/25 3:42 下午
 */
public class Carpenter {

    /**
     * 混合物初始数量
     */
    private static final int INIT_SIZE = 2000000;

    /**
     * 混合物集合
     */
    private Mixture[] mixtures = new Mixture[INIT_SIZE];

    /**
     * 配好对的螺丝
     */
    private Screw[] screws = new Screw[INIT_SIZE / 2];

    public Carpenter() {
        //随机混合螺母和螺帽
        //螺母尺寸
        int[] nutSize = new int[INIT_SIZE / 2];
        //螺帽尺寸
        int[] boltSize = new int[INIT_SIZE / 2];
        for (int i = 0; i < INIT_SIZE / 2; i++) {
            nutSize[i] = i + 1;
            boltSize[i] = i + 1;
        }
        //打乱顺序
        StdRandom.shuffle(nutSize);
        StdRandom.shuffle(boltSize);
        for (int i = 0; i < INIT_SIZE; i++) {
            if (i < INIT_SIZE / 2) mixtures[i] = new Mixture(Mixture.NUT, nutSize[i]);
            else mixtures[i] = new Mixture(Mixture.BOLT, boltSize[i - INIT_SIZE / 2]);
        }
        //打乱顺序
        StdRandom.shuffle(mixtures);
    }

    public Mixture[] getMixtures() {
        return mixtures;
    }

    public void setMixtures(Mixture[] mixtures) {
        this.mixtures = mixtures;
    }

    public Screw[] getScrews() {
        return screws;
    }

    public void setScrews(Screw[] screws) {
        this.screws = screws;
    }

    /**
     * @Author huangy
     * @description //TODO 打印混合物
     * @date 5:54 下午 2020/9/25
     **/
    private void printMixtures() {
        for (Mixture mixture : mixtures) {
            System.out.println(mixture);
        }
    }

    /**
     * @Author huangy
     * @description //TODO 打印螺丝
     * @date 5:54 下午 2020/9/25
     **/
    private void printScrews() {
        for (Screw screw : screws) {
            System.out.println(screw);
        }
    }

    /**
     * @Author huangy
     * @description //TODO 将螺母螺帽配对
     * @date 5:33 下午 2020/9/25
     **/
    public void matchScrew() {
        //先将螺母和螺帽分开
        Nut[] nuts = new Nut[INIT_SIZE / 2];
        Bolt[] bolts = new Bolt[INIT_SIZE / 2];
        int i = 0, j = 0;
        for (Mixture mixture : mixtures) {
            int mixtureSize = mixture.getSize();
            if (Mixture.NUT == mixture.getType()) nuts[i++] = new Nut(mixtureSize);
            else bolts[j++] = new Bolt(mixtureSize);
        }
        //将nuts和bolts排序
        sortNutAndBolt(nuts, bolts, 0, INIT_SIZE / 2 - 1);
        List<Screw> screws = new ArrayList<>();
        for (int k = 0; k < INIT_SIZE / 2; k++) {
            screws.add(new Screw(nuts[k], bolts[k]));
        }
        this.screws = screws.toArray(new Screw[0]);
    }

    /**
     * @param nuts  螺母集合
     * @param bolts 螺帽集合
     * @param low   起始位置
     * @param high  结束位置
     * @return void
     * @Author huangy
     * @description //TODO 对螺母和螺帽进行排序
     * @date 11:29 上午 2020/9/27
     **/
    private void sortNutAndBolt(Nut[] nuts, Bolt[] bolts, int low, int high) {
        if (high <= low) return;
        //选择第一个螺母作为基础螺母
        Nut baseNut = nuts[low];
        Bolt baseBolt = getBaseBoltAndExchange(bolts, baseNut, low, high);
        //通过螺母给螺帽排序
        int index = partition(bolts, baseNut.getSize(), low, high);
        //通过螺帽给螺母排序
        partition(nuts, baseBolt.getSize(), low, high);
        sortNutAndBolt(nuts, bolts, low, index);
        sortNutAndBolt(nuts, bolts, index + 1, high);
    }

    /**
     * @param baseThings 元素集合
     * @param baseSize   基础尺寸
     * @param low        起始位置
     * @param high       结束位置
     * @return void
     * @Author huangy
     * @description //TODO 一趟排序
     * @date 4:36 下午 2020/9/27
     **/
    private int partition(BaseThing[] baseThings, int baseSize, int low, int high) {
        int i = low;
        int j = high + 1;
        while (true) {
            while (baseThings[++i].getSize() < baseSize) if (i == high) break;
            while (baseThings[--j].getSize() > baseSize) if (j == low) break;
            if (i >= j) break;
            exchange(baseThings, i, j);
        }
        exchange(baseThings, low, j);
        return j;
    }

    /**
     * @param bolts 螺帽集合
     * @param nut   螺母
     * @param low   起始位置
     * @param high  结束位置
     * @return cn.com.mdx.sort.practice.nutsbolts.Bolt
     * @Author huangy
     * @description //TODO 为基础螺母找到合适的螺帽，并将其与第一个位置交换
     * @date 3:46 下午 2020/9/27
     **/
    public Bolt getBaseBoltAndExchange(Bolt[] bolts, Nut nut, int low, int high) {
        for (int i = low; i < high; i++) {
            if (nut.getSize() == bolts[i].getSize()) {
                Bolt bolt = bolts[i];
                //将匹配元素与起始位置交换
                exchange(bolts, low, i);
                return bolt;
            }
        }
        return null;
    }

    /**
     * @return void
     * @Author huangy
     * @description //TODO 将螺母和螺帽匹配
     * @date 9:22 上午 2020/9/27
     **/
    public void matchScrewForce() {
        List<Nut> nuts = new ArrayList<>();
        List<Bolt> bolts = new ArrayList<>();
        for (Mixture mixture : mixtures) {
            int mixtureSize = mixture.getSize();
            if (Mixture.NUT == mixture.getType()) nuts.add(new Nut(mixtureSize));
            else bolts.add(new Bolt(mixtureSize));
        }
        List<Screw> screwList = new ArrayList<>();
        //循环配对
        nuts.forEach(nut -> bolts.forEach(bolt -> {
                    if (nut.getSize() == bolt.getSize()) screwList.add(new Screw(nut, bolt));
                })
        );
        screws = screwList.toArray(new Screw[0]);
    }

    /**
     * @param objects 对象集合
     * @param index1  第一个元素位置
     * @param index2  第二个元素位置
     * @return void
     * @Author huangy
     * @description //TODO 交换元素
     * @date 4:13 下午 2020/9/27
     **/
    private void exchange(Object[] objects, int index1, int index2) {
        Object tmp = objects[index1];
        objects[index1] = objects[index2];
        objects[index2] = tmp;
    }

    public static void main(String[] args) {
        //配对
        //testForce();
        testQuick();
    }

    /**
     * 暴力破解方法测试
     */
    private static void testForce() {
        Carpenter carpenter = new Carpenter();
        long before = System.currentTimeMillis();
        carpenter.matchScrewForce();
        long after = System.currentTimeMillis();
        System.out.println("执行时长为：" + (after - before) + "毫秒");
    }

    /**
     * 测试快速执行方法
     */
    private static void testQuick() {
        Carpenter carpenter = new Carpenter();
        //carpenter.printMixtures();
        long before = System.currentTimeMillis();
        carpenter.matchScrew();
        long after = System.currentTimeMillis();
        //carpenter.printScrews();
        System.out.println("执行时长为：" + (after - before) + "毫秒");
    }

}
